package Simple4;

public class TrinaryTree {

	/**
	 * TrinaryTreeNode class.
	 * @author Yue
	 *
	 */
	class TrinaryTreeNode{
		int val;
		TrinaryTreeNode left;
		TrinaryTreeNode mid;
		TrinaryTreeNode right;
		public TrinaryTreeNode(int val) {
			this.val = val;
			this.left = null;
			this.right = null;
			this.mid = null;
		}
	}
	
	/**The root of the tree.**/
	TrinaryTreeNode root;
	
	/**
	 * Constructor
	 */
	public TrinaryTree() {
		this.root = null;
	}
	
	/**
	 * API of insertion
	 * @param val
	 */
	public void insert(int val){
		this.root = insert_helper(val, root);
	}
	
	/**
	 * Insertion of the treenode
	 * @param val	the value of the node
	 * @param node	the node to insert	
	 * @return		the tree after update
	 */
	private TrinaryTreeNode insert_helper(int val, TrinaryTreeNode node){
		if(node==null) node=new TrinaryTreeNode(val);
		else if(val<node.val){
			node.left = insert_helper(val, node.left);
		}
		else if(val>node.val){
			node.right = insert_helper(val, node.right);
		}
		else{
			node.mid = insert_helper(val, node.mid);
		}
		return node;
	}
	
	/**
	 * API of deletion
	 * @param val
	 * @throws Exception 
	 */
	public void delete(int val) throws Exception{
		this.root = delete_helper(val, this.root);
	}
	/**
	 * Delete function of the treenode.
	 * @param val 	value of the node to be removed
	 * @return		the tree need to be updated
	 * @throws Exception  the node with such value doesn't exist in the tree
	 */
	private TrinaryTreeNode delete_helper(int val, TrinaryTreeNode node) throws Exception{
		if(node==null) throw new Exception("No such a node with the given value");
		if(val<node.val){
			node.left = delete_helper(val, node.left);
		}
		else if(val>node.val){
			node.right = delete_helper(val, node.right);
		}
		else{
			//the node has a midnode, use its mid node to replace it.
			if(node.mid!=null){
				node.mid = delete_helper(val, node.mid);
			}
			//if its right node is not empty, use the minimum number on
			//right node to replace it, do it recursively
			else if(node.right!=null){
				TrinaryTreeNode right_min = node.right;
				while (right_min.left!=null) {
					right_min = right_min.left;
				}
				node.val = right_min.val;
				node.right = delete_helper(right_min.val, node.right);
			}
			else{
				node = node.left;
			}
		}
		return node;
	}
	
	/**
	 * API of pre-order print the tree for testing.
	 */
	public void travel(){
		System.out.println("Pre-order travels of the tree.");
		travel_helper(this.root);
		System.out.println();
	}
	
	/**
	 * Print function, do the pre-order travesal recursively.
	 * @param root	the root of current tree.
	 */
	private void travel_helper(TrinaryTreeNode root){
		//pre order travesal
		if(root!=null){
			System.out.print(root.val+",");
			travel_helper(root.left);
			travel_helper(root.mid);
			travel_helper(root.right);
		}
	}
	
	public static void main(String[] args) throws Exception {
		TrinaryTree test = new TrinaryTree();
		try {
			test.insert(5);
			test.insert(4);
			test.insert(5);
			test.insert(9);
			test.insert(2);
			test.insert(7);
			test.insert(2);
			System.out.println("Original tree:");
			test.travel();
			System.out.println();
			System.out.println("Delete node 5");
			test.delete(5);
			test.travel();
		} catch (Exception e) {
			System.out.print(e);
		}
	}
}
